1926G - Vlad and Trouble at MIT - CodeForces Solution

#include <bits/stdc++.h>
using namespace std; 
#define ll long long 
#define all(n) n.begin(),n.end()
void solve(){
 int n; cin>>n; 
    char S; cin>>S; 
    vector<char>  CH = {'C','D','H','S'}; 
    map<char,vector<string>>vsp; 
    vector<pair<string,string>>out; 

    for(int i = 0; i < n * 2; i++){
        string str; cin>>str; 
        vsp[str[1]].push_back(str); 
    }

    int cnt = 0; 

    for(int i = 0; i < 4; i++){
        sort(vsp[CH[i]].begin(),vsp[CH[i]].end()); 
    }

    for(int i = 0; i < 4; i++){
        if(CH[i] != S)
            if(vsp[CH[i]].size() % 2 != 0) cnt++; 
    }

    if(vsp[S].size() % 2 != cnt % 2 or cnt > vsp[S].size()){
        cout<<"IMPOSSIBLE\n"; 
        return ; 
    }

    for(int i = 0; i < 4; i++){
        if(CH[i] != S && vsp[CH[i]].size() % 2 != 0){
            cout<<vsp[CH[i]][vsp[CH[i]].size() - 1]<<' ';
            cout<<vsp[S][vsp[S].size() - 1]<<'\n';
            vsp[CH[i]].pop_back();
            vsp[S].pop_back();  
        }
    }

    for(int i = 0; i < 4; i++){
        if(CH[i] != S){
            for(int j = 0; j < vsp[CH[i]].size(); j+=2){
                cout<<vsp[CH[i]][j]<<' '; 
                cout<<vsp[CH[i]][j+1]<<'\n'; 
            }
        }
    }

    for(int i = 0; i < vsp[S].size(); i+=2){
        cout<<vsp[S][i]<<' '; 
        cout<<vsp[S][i+1]<<'\n'; 
    }

}
int N = 2e5+5; 
vector<ll>ans(N); 
ll dig(int i){
  int sum = 0; 
  while(i){
    sum+=i%10; 
    i/=10; 
  }
 return sum; 
}
bool check(vector<vector<char>>& v, int idx) {
    for (int i = 1; i < v.size() - 1; ++i) {
        for (int j = 1; j < v.size() - 1; ++j) {
            if (((i + j) & 1) == idx) {
                if (v[i][j] == 'B' && v[i - 1][j - 1] == 'B' &&
                 v[i - 1][j + 1] == 'B' && v[i + 1][j - 1] == 'B'
                  && v[i + 1][j + 1] == 'B') {
                    return 0;
                }
            }
        }
    }
    return 1;
}
const int MAX = 1e5 + 10;
string problem;
vector<int> children[MAX];
vector<int> dp_first(MAX),dp_second(MAX);

void dfs(int root = 0){
    
    dp_first[root] = 0;
    dp_second[root] = 0;

    for(auto child : children[root]){
            dfs(child);
            dp_first[root] += min(dp_second[child]+1, dp_first[child]);
            dp_second[root] += min(dp_first[child]+1, dp_second[child]);
        
    }

    if(problem[root] == 'S'){
        dp_first[root] = 1e6;
    }else if(problem[root] == 'P'){
        dp_second[root] = 1e6;
    }
}
void solve2(){
   //  int cnt = 0; 
   // vector<vector<char>> a(7, vector<char>(7));
   //        vector<pair<int, int>> o, e;
   //      for (int i = 0; i < 7; ++i) {
   //          for (int j = 0; j < 7; ++j) {
   //              cin >> a[i][j];
   //          }
   //      }

   //      for (int i = 1; i < 6; ++i) {
   //          for (int j = 1; j < 6; ++j) {
   //              if ((i + j) & 1 && a[i][j] == 'B') {
   //                  o.push_back({i, j});
   //              } else if ((i + j) % 2 == 0 && a[i][j] == 'B') {
   //                  e.push_back({i, j});
   //              }
   //          }
   //      }


   //      int mx = 1e9+5; 
   //      for (int i = 0; i < (1 << int(o.size())); ++i) {
   //           cnt = 0;
   //          for (int j = 0; j < o.size(); ++j) {
   //              if ((1 << j) & i) {
   //                  a[o[j].first][o[j].second] = 'W';
   //                  cnt++;
   //              }
   //          }
   //          mx = (check(a,1) ? min(mx,cnt) : mx); 
          
   //          for (int j = 0; j < o.size(); ++j) {
   //              if ((1 << j) & i) {
   //                  a[o[j].first][o[j].second] = 'B';
   //              }
   //          }
   //      }

   //       int mx_ = 1e9+5; 

   //      for (int i = 0; i < (1 << int(e.size())); ++i) {
   //          cnt = 0;
   //          for (int j = 0; j < e.size(); ++j) {
   //              if ((1 << j) & i) {
   //                  a[e[j].first][e[j].second] = 'W';
   //                  cnt++;
   //              }
   //          }
   //          mx_ = (check(a,0) ? min(mx_,cnt) : mx_); 
   //          for (int j = 0; j < e.size(); ++j) {
   //              if ((1 << j) & i) {
   //                  a[e[j].first][e[j].second] = 'B';
   //              }
   //          }
   //      }

   //      cout << mx + mx_ << '\n';
     int num;
    cin>>num;
    int temp;
    for(int i = 0;i<num;i++){
        children[i].clear();
        if(i != 0){
            cin>>temp;
            children[temp-1].push_back(i);
        }
    }
    cin>>problem;

    dfs();

    cout<<min(dp_first[0],dp_second[0])<<"\n";
        
}
int main() {
   int tt; cin>>tt; 
     while(tt--){
      solve2(); 
     }
 
   // 1000/
    return 0;
}